package com.demo.datastructure.tree;


import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @description: 普通二叉树的相关实现，参照书籍：算法4
 * @author: ljr
 * @time: 2021/5/29 16:50
 */
public class BinarySerachTree2<Key extends Comparable<Key>, Value>{

     private Node root;

     public int size(){
         return size(root);
     }

     private int size(Node node){
         if(node == null) return 0;
         return node.n;
     }

    public void iterator(){
        iterator(root);
    }


    private void iterator(Node node){
        if(node == null) return;
        iterator(node.left);
        System.out.println(node.value);
        iterator(node.right);
    }


    public void leftIterator(){
        leftIterator(root);
    }


    private void leftIterator(Node node){
        if(node == null) return;
        System.out.println(node.value);
        leftIterator(node.left);
        leftIterator(node.right);
    }


    public void rightIterator(){
        rightIterator(root,0);
    }


    private void rightIterator(Node node, int level){
        if(node == null) return;
        rightIterator(node.left, level+1);
        rightIterator(node.right, level+1);
        System.out.println(node.value+" "+level);
    }


     public Value get(Key key){
         return null;
     }

     private Value get(Node node, Key key){
         Node crtNode = node;
         while(crtNode != null){
            int cmp = key.compareTo(crtNode.key);
            if(cmp > 0) crtNode = crtNode.right;
            else if(cmp < 0) crtNode = crtNode.left;
            else return crtNode.value;
         }
         return null;
     }

    private Value get2(Node node, Key key){
        if(node == null){ return null; }
        int cmp = key.compareTo(node.key);
        if(cmp > 0)  return get2(node.right, key);
        else if(cmp < 0) return get2(node.left, key);
        else return node.value;
    }

     //二叉树中插入数据
     public void put(Key key, Value value){
         root = put(root,key,value);
     }

     private Node put(Node node, Key key, Value value){
         if(node == null){
             return new Node(key,value,1);
         }
         int cmp = key.compareTo(node.key);
         if(cmp > 0){ node.right = put(node.right,key,value);}
         else if(cmp < 0){  node.left = put(node.left, key,value);}
         else node.value = value;
         int n = size(node.left)+size(node.right)+1;
         node.n = n;
         return node;
     }

    //返回最小key
     public Key min(){
         if(root == null){ return null;}
         return min(root).key;
     }


    private Node min(Node node){
        if(node.left == null){ return node;}
        return min(node.left);
    }

    //返回最大key
    public Key max(){
        if(root == null){ return null;}
        return max(root).key;
    }

    private Node max(Node node){
         if(node.right == null){ return  node;}
         return max(node.right);
    }

    //找出二叉树中的第n个元素
    public Key select(int key){
        Node node =  select(root,key);
        return  node == null ? null : node.key;
    }

    private Node select(Node node,int key){
        if(node == null){ return null;}
        int size = size(node.left);
        if(key < size) return select(node.left, key);
        else if(key > size) return select(node.right, key-size-1);
        else return node;
    }

    public Key select2(int key){
        Node node =  select2(root,key);
        return  node == null ? null : node.key;
    }

    private Node select2(Node node,int key){
        Node current = node;
        while (current != null){
           int size = size(current.left);
           if(key > size){
               key = key-size-1;
               current = current.right;
           }else if(key < size){
               current = current.left;
           }else{
               return current;
           }
        }
        return null;
    }



    //获取二叉树中某个key对应的下标
    //左子节点为-1，减去右子节点数
    //右子节点为+1，加上左子节点数
    public int rank(Key key){
        return rank(root, key);
    }

    private int rank(Node node, Key key){
         if(node == null){ return 0; }
         int cmp = key.compareTo(node.key);
         if(cmp > 0) return  1+rank(node.right, key)+size(node.left);
         else if(cmp < 0) return rank(node.left, key);
         else return size(node.left);
    }


    //获取二叉树中某个key对应的下标,非递归版本
    public int rank2(Key key){
        return rank2(root, key);
    }

    private int rank2(Node node, Key key){
        if(node == null){ return 0;}
        Node current = node;
        int rank = size(current.left);
        while (current != null){
            int cmp = key.compareTo(current.key);
            if(cmp > 0){
                current = current.right;
                if(current != null){
                    rank = rank+1+size(current.left);
                }
            }else if(cmp < 0){
                current = current.left;
                if(current != null){
                    rank = rank-1-size(current.right);
                }
            }else{
                return rank;
            }
        }
        return 0;
    }


    //删除最小节点
    public void deleteMin(){
        root = deleteMin(root);
    }

    private Node deleteMin(Node node){
        if(node == null){ return null; }
        if(node.left == null) return node.right;
        node.left = deleteMin(node.left);
        node.n = size(node.left)+size(node.right)+1;
        return node ;
    }


    //二叉树节点删除
    public void delete(Key key){
         root = delete(root,key);
    }

    private Node delete(Node node, Key key){
        if(node == null){ return null; }
        int cmp = key.compareTo(node.key);
        if(cmp > 0) node.right = delete(node,key);
        else if(cmp < 0) node.left = delete(node,key);
        else{
            if(node.left == null){
                return node.right;
            }else if(node.right == null){
                return node.left;
            }else{
                Node t = node;
                Node x = min(t.right);
                t.right = deleteMin(t.right);
                x.right = t.right;
                x.left = t.left;
                return x;
            }
        }
        node.n = size(node.left)+size(node.right)+1;
        return node;
    }

    //二叉树范围查找
    public Iterable<Key>  keys(){
        return  keys(min(),max());
    }

    public Iterable<Key> keys(Key low, Key high){
        Queue<Key> queue = new LinkedList<Key>();
        keys(root,queue,low,high);
        return queue;
    }

    private void keys(Node node, Queue<Key> queue,
                      Key low,
                      Key high) {
         if(node == null){ return; }
         int cmpLow = low.compareTo(node.key);
         int cmpHigh = high.compareTo(node.key);
         if(cmpLow == -1){
             keys(node.left, queue, low, high);
         }

         if(cmpLow <= 0 && cmpHigh >= 0){
             queue.add(node.key);
         }

         if(cmpHigh == 1){
             keys(node.right, queue, low, high);
         }
    }


    //求找一个key的平均比较次数
    public int avgCompares(){
       if(root == null){ return 0;}
       return  root.n/floor()+1;
    }


    //获取树的层数
    public int floor() {
       return floor(root);
    }

    private int floor(Node node){
        if(node == null){ return  0; }
        return Math.max(floor(node.left), floor(node.right))+1;
    }

    public boolean isBalanced(){
         return isBalanced(root);
    }

    public boolean isBalanced(Node nodeTree) {
        if(nodeTree == null){ return true; }
        Deque<Node> deque = new LinkedList<>();
        deque.add(nodeTree);
        int level = 0;
        int drawLevel = 0;
        int num = 1;
        while(!deque.isEmpty()){
            int n = deque.size();
            for(int i = 0; i < n; i++){
                Node node = deque.pop();
                if(node.left != null)deque.add(node.left);
                if(node.right != null)deque.add(node.right);
            }
            num = num*2;
            level++;
            if(num != deque.size() && drawLevel == 0){
                drawLevel = level;
            }

            if(level - drawLevel > 1){
                return false;
            }

        }
        return drawLevel == level || drawLevel+1 == level;
    }

    private class Node{
        private Key key;
        private Value value;
        private Node left;
        private Node right;
        private int n;

        public Node(Key key, Value value, int n) {
            this.key = key;
            this.value = value;
            this.n = n;
        }
    }


    public static void main(String[] args) {
        BinarySerachTree2<Integer,Integer> tree = new BinarySerachTree2<>();
        tree.put(33,33);
        tree.put(17,17);
        tree.put(50,50);
        tree.put(13,13);
        tree.put(18,18);
        tree.put(34,34);
        tree.put(58,58);
        tree.put(16,16);
        tree.put(25,25);
        tree.put(51,51);
        tree.put(66,66);
        tree.put(19,19);
        tree.put(27,27);
        //System.out.println(tree.select(10));
        //System.out.println(tree.select2(10));
        System.out.println(tree.isBalanced());
        tree.leftIterator();
        System.out.println("=======================");
        tree.rightIterator();
        //tree.iterator();
        //Iterable<Integer> trees = tree.keys();
        //trees.forEach(x -> System.out.println(x));
    }

}
